package com.leecode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 3. 无重复字符的最长子串
 * <p>
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 */
public class Leet3 {
    public static void main(String[] args) {
        System.out.println(new Leet3().lengthOfLongestSubstring2("abcabcbb"));

//        System.out.println(findMedianSortedArrays(new int[]{1,3}, new int[]{2,4}));
    }

    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), gap = 0, max = 0;
        HashMap map = new HashMap();
        for (int i = 0, j = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max((int) map.get(s.charAt(j)) + 1, i);
            }
            gap = j - i + 1;
            max = Math.max(max, gap);
            map.put(s.charAt(j), j);
        }
        return max;
    }

    public int lengthOfLongestSubstring2(String s) {
        if (s == null || s.length()==0) return 0;
        if (s.length() == 1) return 1;

        int b1 = 0;//第一反应,double reference
        int b2 = b1 + 1;

        int max = 1;
        h:
        while (b2 <= s.length() - 1) {
            for (int a = b1; a < b2; a++) {//这是我自己想出来的,上面标准答案的利用hash优化多次比较居然更慢?!!
                if (s.charAt(a) == s.charAt(b2)) {
                    b1 = a + 1;
                    b2++;
                    continue h;
                }
            }
            max = Math.max(max, b2 - b1 + 1);
            b2++;
        }

        return max;
    }


    //4
    public static double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A;
            A = B;
            B = temp;
            int tmp = m;
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;


    }

}
